#!/usr/bin/env python3

'''
PROBLEM 50

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?
'''

from itertools import combinations

def getprimes(limit):
	primes = set()
	nums = range(2,limit+1)
	marked = [0] * limit
	p = 2
	for p in nums:
		if not marked[p-2]:
			n = 2
			a = p*n
			while(a <= limit):
				marked[a-2] = 1
				n = n + 1
				a = p*n
	for x in range(limit-1):
		if not marked[x]:
			primes.add(nums[x])
	return primes

def findsum(limit):
    primes_all = sorted(list(getprimes(limit)))
    cut = int(len(primes_all) * .0075)
    primes = primes_all[:cut]
    answer = []
    longest = 0
    longest_possible = cut
    for x in range(len(primes)):
        current = []
        rng = len(primes)-x
        if longest_possible < len(primes)-x:
            rng = longest_possible
        for y in range(rng):
            current.append(primes[x+y])
            if sum(current) > limit:
                if x == 0:
                    longest_possible = y
                break
            if sum(current) in primes_all and y > longest:
                answer = current * 1
                longest = y
        if len(primes) - x < longest:
            print(x/len(primes))
            print(str(len(answer))+"/"+str(len(primes))+"="+str(len(answer)/len(primes)))
            return answer
    return answer
    
answer = findsum(1000000)
print(sum(answer))
print("-----")
print(answer)
